package cn.iocoder.algorithm.leetcode.no0200;

/**
 * 并查集
 */
public class Solution02 {

    private class UnionFind {

        private int counts;
        private int[] array;
        private int n;
        private int m;

        public UnionFind(char[][] grid) {
            // 初始化参数
            this.n = grid.length;
            if (n == 0) {
                return;
            }
            this.m = grid[0].length;
            // 初始化 array
            this.array = new int[n * m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    // 设置值
                    int index = this.index(i, j);
                    if (grid[i][j] == '0') {
                        array[index] = -1;
                        continue;
                    }
                    array[index] = index;
                    // 计数++
                    counts++;
                    // 连接
                    this.join(index, this.index(i - 1, j)); // 上边
                    this.join(index, this.index(i, j - 1)); // 左边
                }
            }
        }

        private int index(int i, int j) {
            if (i < 0 || j < 0) {
                return -1;
            }
            return i * m + j;
        }

        private void join(int p, int q) {
            if (p < 0 || q < 0) {
                return;
            }
            if (array[p] == -1 || array[q] == -1) {
                return;
            }
            int pRoot = this.find(p);
            int qRoot = this.find(q);
            if (pRoot == qRoot) {
                return;
            }
            counts--;
            if (pRoot > qRoot) {
                array[pRoot] = qRoot;
            } else {
                array[qRoot] = pRoot;
            }
        }

        private int find(int i) {
            // 寻找 root
            int root = i;
            while (array[root] != root) {
                root = array[root];
            }

            // 路径压缩
            while (i != root) {
                int tmp = array[i];
                array[i] = root;
                i = tmp;
            }

            return root;
        }

        public int getCount() {
            int sum = 0;
            for (int i = 0; i < array.length; i++) {
                if (array[i] == i) {
                    sum++;
                }
            }
            return sum;
        }

//        public void printf() {
//            int index = 0;
//            for (int i = 0; i < ) {
//
//            }
//        }

    }

    public int numIslands(char[][] grid) {
        UnionFind uf = new UnionFind(grid);
        return uf.getCount();
    }

    public static void main(String[] args) {
//        char[][] grid = new char[][]{
//                {'1', '1', '1', '1', '0'},
//                {'1', '1', '0', '1', '0'},
//                {'1', '1', '0', '0', '0'},
//                {'0', '0', '0', '0', '0'}
//        };
//        char[][] grid = new char[][]{
//                {'1', '1', '0', '0', '0'},
//                {'1', '1', '0', '0', '0'},
//                {'0', '0', '1', '0', '0'},
//                {'0', '0', '0', '1', '1'}
//        };
//        char[][] grid = new char[][]{
//                {'1'},
//                {'1'}
//        };
//        char[][] grid = new char[][]{
//                {'1','0','0','1','1','1','0','1','1','0','0','0','0','0','0','0','0','0','0','0'},
//                {'1','0','0','1','1','0','0','1','0','0','0','1','0','1','0','1','0','0','1','0'},
//                {'0','0','0','1','1','1','1','0','1','0','1','1','0','0','0','0','1','0','1','0'},
//                {'0','0','0','1','1','0','0','1','0','0','0','1','1','1','0','0','1','0','0','1'},
//                {'0','0','0','0','0','0','0','1','1','1','0','0','0','0','0','0','0','0','0','0'},
//                {'1','0','0','0','0','1','0','1','0','1','1','0','0','0','0','0','0','1','0','1'},
//                {'0','0','0','1','0','0','0','1','0','1','0','1','0','1','0','1','0','1','0','1'},
//                {'0','0','0','1','0','1','0','0','1','1','0','1','0','1','1','0','1','1','1','0'},
//                {'0','0','0','0','1','0','0','1','1','0','0','0','0','1','0','0','0','1','0','1'},
//                {'0','0','1','0','0','1','0','0','0','0','0','1','0','0','1','0','0','0','1','0'},
//                {'1','0','0','1','0','0','0','0','0','0','0','1','0','0','1','0','1','0','1','0'},
//                {'0','1','0','0','0','1','0','1','0','1','1','0','1','1','1','0','1','1','0','0'},
//                {'1','1','0','1','0','0','0','0','1','0','0','0','0','0','0','1','0','0','0','1'},
//                {'0','1','0','0','1','1','1','0','0','0','1','1','1','1','1','0','1','0','0','0'},
//                {'0','0','1','1','1','0','0','0','1','1','0','0','0','1','0','1','0','0','0','0'},
//                {'1','0','0','1','0','1','0','0','0','0','1','0','0','0','1','0','1','0','1','1'},
//                {'1','0','1','0','0','0','0','0','0','1','0','0','0','1','0','1','0','0','0','0'},
//                {'0','1','1','0','0','0','1','1','1','0','1','0','1','0','1','1','1','1','0','0'},
//                {'0','1','0','0','0','0','1','1','0','0','1','0','1','0','0','1','0','0','1','1'},
//                {'0','0','0','0','0','0','1','1','1','1','0','1','0','0','0','1','1','0','0','0'}
//        };


        char[][] grid = new char[][]{
                {'0','1'},
                {'1','0'},
//                {'0','1','1','0','0','0','1','1','1','0','1','0','1','0','1','1','1','1','0','0'},
//                {'0','1','0','0','0','0','1','1','0','0','1','0','1','0','0','1','0','0','1','1'},
//                {'0','0','0','0','0','0','1','1','1','1','0','1','0','0','0','1','1','0','0','0'}
        };

//        for (int i = 0; i < grid.length; i++) {
//            for (int j = 0; j < grid[0].length; j++) {
//                System.out.print(grid[i][j] + "\t");
//            }
//            System.out.println();
//        }

        Solution02 solution02 = new Solution02();
        System.out.println(solution02.numIslands(grid));

//        Solution solution = new Solution();
//        System.out.println(solution.numIslands(grid));
    }

}
